#include"game.h"
#include<bits/stdc++.h>
using namespace std;
const int NN=5004;
int ans[NN],n;
mt19937 rnd(time(0));
void solve(vector<int>t,vector<int>x)
{
	if(!t.size())
		return;
	if(t.size()==1)
	{
		ans[t[0]]=t[0];
		return;
	}
	vector<int>p;
	shuffle(x.begin(),x.end(),rnd);
	for(int i=1,j=0;i<=n;i++)
	{
		if(ans[i])
			p.push_back(ans[i]);
		else
			p.push_back(x[j++]);
	}
	int w=count(p);
	vector<int>np[5];
	for(int i=1;i<t.size();i++)
	{
		swap(p[t[0]-1],p[t[i]-1]);
		np[count(p)-w+2].push_back(t[i]);
		swap(p[t[0]-1],p[t[i]-1]);
	}
	if(!np[2].size()&&!np[3].size()&&!np[4].size())
	{
		ans[t[0]]=p[t[0]-1];
		for(int i=0;i<np[0].size();i++)
			ans[np[0][i]]=p[np[0][i]-1];
		vector<int>tmp;
		for(int i=0;i<np[1].size();i++)
			tmp.push_back(p[np[1][i]-1]);
		solve(np[1],tmp);
	}
	else
	{
		assert(!np[0].size());
		if(!np[4].size())
		{
			assert(np[3].size()==2);
			swap(p[np[3][0]-1],p[np[3][1]-1]);
			w=count(p);
			for(int i=0;i<np[3].size();i++)
			{
				swap(p[t[0]-1],p[np[3][i]-1]);
				np[count(p)-w+2].push_back(np[3][i]);
				swap(p[t[0]-1],p[np[3][i]-1]);
			}
			assert(np[3].size()==2);
			np[3].clear();
		}
		assert(np[4].size()==1&&!np[3].size());
		ans[t[0]]=p[np[4][0]-1];
		ans[np[4][0]]=p[t[0]-1];
		for(int i=0;i<np[1].size();i++)
			ans[np[1][i]]=p[np[1][i]-1];
		vector<int>tmp;
		for(int i=0;i<np[2].size();i++)
			tmp.push_back(p[np[2][i]-1]);
		solve(np[2],tmp);
	}
}
vector<int>guess(int N,int limit)
{
	n=N;
	vector<int>t;
	for(int i=1;i<=n;i++)
		t.push_back(i);
	solve(t,t);
	t.clear();
	for(int i=1;i<=n;i++)
		t.push_back(ans[i]);
	return t;
}
